Parity protection is used in computer systems to protect against loss of data on one storage device by computing a parity value determined by summing (usually modulo 2) data of a particular word size (usually one bit) across a number of similar storage devices holding different data, and then storing the result on an additional similar storage device. The data is then protected against the loss of any of the storage devices. In the case that the device storing the parity is lost, the parity can be regenerated from the data. In the case that one of the data devices is lost, the data can be regenerated by adding the contents of the surviving data devices together and then subtracting the result from the stored parity. In the usual case, the parity is computed on vectors one bit wide, composed of bits in corresponding positions in each of the storage devices. In this case, addition and subtraction are both equivalent to an exclusive-or logical operation, and the addition and subtraction operations are replaced by exclusive-or operations. It is also the case that when the parity is computed on vectors one bit wide, that the stored parity can be either the computed sum or its complement. These are referred to as even and odd parity respectively.
An aspect of parity protection of data is that it provides protection against only one failure. The original data can be corrected in the case of the failure of any single storage device. However, in the case of multiple simultaneous failures, no such protection is provided, and in fact such failures might not be detected.
There is a need in highly reliable computer systems to provide reliable data storage in the case of multiple failures. Such reliability is often provided by more complex coding schemes on the data. However, such coding schemes have some disadvantages. First, they may greatly increase the amount of storage space required to store the redundant data. Second, they may greatly increase the amount of time required to regenerate the redundant data when some data is modified. Third, they increase the time required to regenerate lost data when failures occur.